#!/usr/bin/env python3
#coding:utf-8

__author__ = 'xmxoxo'

'''
题目C:
输入一串带嵌套的括号（只有小括号）的表达式，判断括号的匹配是否合法，
如果合法的话输出每一对括号及其里边包括的所有内容。
例如输入是：
(5*(9+6*(2-30)-(10/2))-4)*8
输出是：
(2-30)
(10/2)
(9+6*(2-30)-(10/2))
(5*(9+6*(2-30)-(10/2))-4)
如果输入：
((5-1)*7
输出：
不合法！


'''

#返回字符串txt中char出现的所有位置
#返回一个list
def getAllchar (txt,char):
    import re
    lst = [m.start() for m in re.finditer(char,txt)]
    return lst



#括号匹配判断  ** 函数未验证 改用新函数 ***
#参数： express 表达式
#返回： 直接输出结果
def main1 (express):
    pass
    #用一个栈来存放数据,list模拟栈，前面是底，后面是头
    lstStack = []
    #用字符串来保存出栈后内容
    strOut = ''
    #用list来保存所有的输出结果；
    lstRet = []
    #开始扫描表达式
    strExp = '' #这个用来保存临时的表达式
    for x in list(express) :
        #如果是左括号，则看下表达式有没东西，有就放进栈中
        if x == '(':
            #lstSTack.append(x)
            if strExp:
                lstSTack.append(strExp)
                strExp = "("
            continue
        #如果是右括号，那就出栈了
        if x == ')':
            if strExp:
                #lstRet.append(strExp)
                strOut += strExp + ')'
            if lstStack:
                #lstRet.append(lstStack.pop())
                strOut = lstStack.pop() + strOut 
            lstRet.append(strOut)
            strExp = ''
            continue
        
        #如果不是括号，就是其它东西了，也不用处理了，连成一串吧
        strExp += x

        #输出调试信息看是否与手工推理相同
        print(lstStack,lstRet,strOut)
    #最后检查栈是否为空
    if lstStack:
        pass
        print('不合法！')
    else:
        for x in lstRet :
            print(x)


#抽象后的简洁算法
def main (express):
    #找出左右括号的位置
    lstA = getAllchar(express,"\(")
    lstB = getAllchar(express,"\)")
    #快速判断下：数量不等直接结束
    if len(lstA) != len(lstB):
        pass
        #print('不合法！')
        #return
    #合并成字典：
    dictExp = {}
    dictExp.update({x:'(' for x in lstA})
    dictExp.update({x:')' for x in lstB})   
    #按位置索引排序下
    dictExp = dict(sorted(dictExp.items(), key = lambda x:x[0]))

    #堆栈存放数据
    lstStack = []
    #用list来保存所有的输出结果；
    lstRet = []
    #开始扫描
    for x in dictExp:
        if dictExp[x] == '(':
            lstStack.append(x)
            #输出调试信息
            #print('debug:',lstStack,lstRet)
        if dictExp[x] == ')':
            if lstStack:
                pos = lstStack.pop()
                lstRet.append((pos,x))
                #输出调试信息
                #print('debug:',lstStack,lstRet)
            else:
                print('不合法！位置：%d' % (x))
                print('%s \n%s^......pos: %d need \'(\' \n' % (express,str(' '*x),x))
                return
    #检查栈是否为空
    if lstStack :
        pos = lstStack.pop()
        print('不合法！位置：%d' % (pos))
        print('%s \n%s^......pos: %d need \')\' \n' % (express,str(' '*pos),pos))
        return
    #根据结果输出字符串
    print('所有括号对:')
    for x in lstRet :
        print(express[x[0]:x[1]+1])
    print('-'*30)
        
  

if __name__ == '__main__':
    pass
    main('(5*(9+6*(2-30)-(10/2))-4)*8')
    main('((5-1)*7')
    main('(3*x+5)-7)5-1)*7')
    main('5*(3+2/3)-(7+(5/3)*7')


'''
运行结果：

---------- python36 ----------
所有括号对:
(2-30)
(10/2)
(9+6*(2-30)-(10/2))
(5*(9+6*(2-30)-(10/2))-4)
------------------------------
不合法！位置：0
((5-1)*7 
^......pos: 0 need ')' 

不合法！位置：9
(3*x+5)-7)5-1)*7 
         ^......pos: 9 need '(' 

不合法！位置：10
5*(3+2/3)-(7+(5/3)*7 
          ^......pos: 10 need ')' 


输出完成 (耗时: 0 秒)

'''